import sys
from copy import deepcopy

class Vertex:
    def __init__(self, id, label):
        self.id = id
        self.label = label
        self.adjacent = set([])
        self.connection = set([])
    def add_adjacent(self, vertex_id):
        self.adjacent.add(vertex_id)
    def add_connection(self, edge_id):
        self.connection.add(edge_id)

class Edge:
    def __init__(self, id, vertex1, vertex2, label):
        self.id = id
        self.vertex1 = vertex1
        self.vertex2 = vertex2
        self.label = label
      
class Graph:
    def __init__(self):
        self.vertices = {}
        self.edges = {}
        self.vertex_count = 0
        self.edge_count = 0
    def add_vertex(self, vertex):
        self.vertices[vertex.id] = vertex
        self.vertex_count += 1
    def add_edge(self, edge):
        self.edges[edge.id] = edge
        (self.vertices[edge.vertex1]).add_adjacent(edge.vertex2)
        (self.vertices[edge.vertex2]).add_adjacent(edge.vertex1)
        (self.vertices[edge.vertex1]).add_connection(edge.id)
        (self.vertices[edge.vertex2]).add_connection(edge.id)                
        self.edge_count += 1
    def get_vertex(self, vertex_id):
        return self.vertices[vertex_id]
    def get_edge(self, edge_id):
        return self.edges[edge_id]        
    def get_adjacent_vertices(self, vertex_id):
        return (self.vertices[vertex_id]).adjacent
    def get_vertex_order(self):
        return self.vertices.keys()
    def is_min(self):
        minimal = True
        ec = EdgeOrder(self, self.get_vertex_order())
        curr_code = ec.get()
        for i in DFS(self):
            eo = EdgeOrder(self, i)
            possible_code = eo.get()
            if possible_code < curr_code:
                minimal = False
                break               
        return minimal
    def contains_edge(self, vertex_id1, vertex_id2, label):
        vertex_edges1 = (self.get_vertex(vertex_id1)).connection
        vertex_edges2 = (self.get_vertex(vertex_id2)).connection
        common = vertex_edges1.intersection(vertex_edges2)
        if len(common) == 0:
            return False
        else:
            for edge_id in common:
                edge = self.get_edge(edge_id)
                return edge.label == label
    def dump(self):
        for vertex_id in self.vertices.keys():
            print "v",
            print self.vertices[vertex_id].id,
            print self.vertices[vertex_id].label
        for edge_id in self.edges.keys():
            print "u",
            print self.edges[edge_id].vertex1,
            print self.edges[edge_id].vertex2,
            print self.edges[edge_id].label

class DFS:
    def __init__(self, graph):
        self.graph = graph
        self.stack = []
        for vertex_id in graph.vertices.keys():
            self.stack.append([vertex_id])
    def __iter__(self):
        if len(self.stack) != 0: 
            complete = False        
        while(not complete and len(self.stack) != 0):
            curr = self.stack.pop()
            if len(curr) == self.graph.vertex_count:
                yield curr
            else:
                current_set = set(curr)
                expansion_set = set([])
                for vertex_id in curr:
                    for adjacent_vertex_id in self.graph.get_adjacent_vertices(vertex_id):
                        expansion_set.add(adjacent_vertex_id)
                expansion_set = expansion_set.difference(current_set)               
                for vertex_id in expansion_set:
                    new = deepcopy(curr)
                    new.append(vertex_id)
                    self.stack.insert(0, new)
                    
class EdgeOrder:
    def __init__(self, graph, vertex_order):
        self.graph = graph
        self.vertex_order = vertex_order
        
    def compare(self, edge_id1, edge_id2):
        edge1 = self.graph.get_edge(edge_id1)
        edge2 = self.graph.get_edge(edge_id2)
        edge_tuple1 = tuple(sorted([self.vertex_order.index(edge1.vertex1),
                              self.vertex_order.index(edge1.vertex2)]))
        edge_tuple2 = tuple(sorted([self.vertex_order.index(edge2.vertex1),
                              self.vertex_order.index(edge2.vertex2)]))
        if edge_tuple1 > edge_tuple2:
            return 1
        else:
            return -1
        
    def get(self):
        edge_id_order = sorted(self.graph.edges.keys(), self.compare)
        edge_order = []
        for edge_id in edge_id_order:
            if self.vertex_order.index((self.graph.get_edge(edge_id)).vertex1) < self.vertex_order.index((self.graph.get_edge(edge_id)).vertex2):
                edge_order.append((self.vertex_order.index((self.graph.get_edge(edge_id)).vertex1),
                                   self.vertex_order.index((self.graph.get_edge(edge_id)).vertex2),
                                   (self.graph.get_vertex((self.graph.get_edge(edge_id)).vertex1)).label,
                                   (self.graph.get_edge(edge_id)).label,
                                   (self.graph.get_vertex((self.graph.get_edge(edge_id)).vertex2)).label))
            else:
                edge_order.append((self.vertex_order.index((self.graph.get_edge(edge_id)).vertex2),
                                   self.vertex_order.index((self.graph.get_edge(edge_id)).vertex1),
                                   (self.graph.get_vertex((self.graph.get_edge(edge_id)).vertex2)).label,
                                   (self.graph.get_edge(edge_id)).label,
                                   (self.graph.get_vertex((self.graph.get_edge(edge_id)).vertex1)).label))
                
        return tuple(edge_order)

class Expansions:
    def __init__(self, query, database, mapping):
        self.query = query
        self.database = database
        self.mapping = mapping
        self.back_mapping = {}
        for vertex_id in mapping.keys():
            self.back_mapping[mapping[vertex_id]] = vertex_id
    def get(self):
        extensions = set([])
        new_vertex_id = self.query.vertex_count + 1
        for query_vertex_id in self.mapping.keys():
            vertex = self.database.get_vertex(self.mapping[query_vertex_id])
            for edge_id in vertex.connection:
                edge = self.database.get_edge(edge_id)
                vertex1_label = (self.database.get_vertex(edge.vertex1)).label
                vertex2_label = (self.database.get_vertex(edge.vertex2)).label
                if self.back_mapping.has_key(edge.vertex1):
                    if self.back_mapping.has_key(edge.vertex2):                
                        if not self.query.contains_edge(self.back_mapping[edge.vertex1], self.back_mapping[edge.vertex2], edge.label):
                            if self.back_mapping[edge.vertex1] < self.back_mapping[edge.vertex2]:
                                extensions.add((self.back_mapping[edge.vertex1], self.back_mapping[edge.vertex2], edge.label, vertex1_label, vertex2_label))
                            else:
                                extensions.add((self.back_mapping[edge.vertex2], self.back_mapping[edge.vertex1], edge.label, vertex2_label, vertex1_label)) 
                    else:                        
                        extensions.add((self.back_mapping[edge.vertex1], new_vertex_id, edge.label, vertex1_label, vertex2_label))                        
                else:
                    if self.back_mapping.has_key(edge.vertex2):
                        extensions.add((self.back_mapping[edge.vertex2], new_vertex_id, edge.label, vertex2_label, vertex1_label))
        return extensions

class CheckMapping:
    def __init__(self, query, database, mapping):
        self.query = query
        self.database = database
        self.mapping = mapping
    def check(self):
        for query_edge_id in self.query.edges.keys():
            edge = self.query.get_edge(query_edge_id)
            if self.mapping.has_key(edge.vertex1) and self.mapping.has_key(edge.vertex2):
                if not self.database.contains_edge(self.mapping[edge.vertex1], self.mapping[edge.vertex2], edge.label):
                    return False
            else:
                return False
        return True

class GenerateMappings:
    def __init__(self, query, database):
        self.query = query
        self.database = database
        self.mapping = {}
    def get(self):        
        for query_vertex_id in self.query.vertices.keys():
            query_vertex = self.query.get_vertex(query_vertex_id)
            for database_vertex_id in self.database.vertices.keys():
                database_vertex = self.database.get_vertex(database_vertex_id)
                if query_vertex.label == database_vertex.label and\
                   len(query_vertex.adjacent) <= len(database_vertex.adjacent):
                    self.add_mapping(query_vertex_id, database_vertex_id)
        if len(self.mapping.keys()) != self.query.vertex_count:
            self.mapping = {}
        return self.mapping
        
    def add_mapping(self, fm, to):
        if self.mapping.has_key(fm):
            (self.mapping[fm]).add(to)
        else:
            self.mapping[fm] = set([to])

class PermuteMappings:
    def __init__(self, mapping):
        self.mapping = mapping
        self.stack = []
        if len(self.mapping.keys()) > 0:
            for vertex_id in self.mapping[1]:
                curr_mapping = {}
                curr_mapping[1] = vertex_id
                self.stack.append(curr_mapping)
    def __iter__(self):
        while(len(self.stack) != 0):
            curr = self.stack.pop()
            if len(curr.keys()) == len(self.mapping.keys()):
                yield curr
            else:
                for vertex_id in self.mapping[len(curr.keys()) + 1]:
                    new = deepcopy(curr)
                    unassigned = True
                    for assigned_vertex_id in curr.keys():
                        if curr[assigned_vertex_id] == vertex_id:
                            unassigned = False
                            break
                    if unassigned:    
                        new[len(curr.keys()) + 1] = vertex_id
                        self.stack.insert(0, new)
class Enumerate:
    def __init__(self, query, database):
        self.query = query
        self.database = database
        g = GenerateMappings(self.query, self.database)
        self.mappings = g.get()
        self.expansions = set([])
    def get(self):
        found = False
        for seperated_mapping in PermuteMappings(self.mappings):
            possible = CheckMapping(self.query, self.database, seperated_mapping)
            if possible.check():
                found = True                
                e = Expansions(self.query, self.database, seperated_mapping)
                for expansion in e.get():
                    self.expansions.add(expansion)                    
        return (found, self.expansions)

class Transactions:
    def __init__(self):
        self.db = {}
        self.count = 0
        self.vertex_labels = set([])
    def add_transaction(self, transaction):
        self.count += 1
        self.db[self.count] = transaction
    def read_transactions(self, filename):
        input_file = open(filename, 'r')
        dirty = False
        for line in input_file:
            words = line.split()
            if len(words) > 0:
                if words[0] == "t":
                    if dirty:
                        self.add_transaction(curr_transaction)
                    else:
                        dirty = True
                    curr_transaction = Graph()
                    edge_count = 0
                elif words[0] == 'v':
                    curr_vertex = Vertex(int(words[1]), words[2])
                    curr_transaction.add_vertex(curr_vertex)
                    self.vertex_labels.add(words[2])
                elif words[0] == 'u':
                    edge_count += 1
                    curr_edge = Edge(edge_count, int(words[1]), int(words[2]), words[3])
                    curr_transaction.add_edge(curr_edge)
        self.add_transaction(curr_transaction)
        input_file.close()
    def get_initial_graphs(self):
        initial_graphs = []
        for vertex_label in self.vertex_labels:
            curr_graph = Graph()
            curr_vertex = Vertex(1, vertex_label)
            curr_graph.add_vertex(curr_vertex)
            initial_graphs.append(curr_graph)
        return initial_graphs
    def enumerate(self, query, old_tids):
        sys.stdout.flush()
        possible_expansions = set([])
        new_tids = set([])
        for database_key in old_tids:
            curr_database = self.db[database_key]
            ennumeration = Enumerate(query, curr_database)
            result = ennumeration.get()
            if result[0]:
                new_tids.add(database_key)
                for expansion in result[1]:
                    possible_expansions.add(expansion)
            sys.stdout.flush()  
        sys.stdout.flush()
        return (new_tids, possible_expansions)

class ApplyExpansions:
    def __init__(self, graph, expansions):
        self.graph = graph
        self.expansions = expansions
        self.expanded_graphs = []
    def get(self):
        for expansion in self.expansions:
            curr = deepcopy(self.graph)
            if expansion[1] > self.graph.vertex_count:    
                curr_vertex = Vertex(expansion[1], expansion[4])
                curr.add_vertex(curr_vertex)
            curr_edge = Edge(curr.edge_count + 1, expansion[0], expansion[1], expansion[2])
            curr.add_edge(curr_edge)
            self.expanded_graphs.append(curr)
        return self.expanded_graphs
                    
transactions = Transactions()
transactions.read_transactions(sys.argv[1])
threshold = int(sys.argv[2])
maxsize = int(sys.argv[3])
stack = []
for initial_subgraph in transactions.get_initial_graphs():
    stack.append((initial_subgraph, transactions.db.keys()))
count = 0
print len(stack),
print "initial subgraphs..."
while(len(stack) != 0):
    curr_graph = stack.pop()
    result = transactions.enumerate(curr_graph[0], curr_graph[1])
    expansion_object = ApplyExpansions(curr_graph[0], result[1])
    expanded_graphs = expansion_object.get()
    for expanded_graph in expanded_graphs:
        if expanded_graph.is_min() and len(result[0]) >= threshold and expanded_graph.edge_count <= maxsize:
            expanded_graph.dump()
            print ""
            count += 1
            stack.insert(0, (expanded_graph, result[0]))

print "Found ",
print count,
print "subgraphs..."

            


